let arr = [2, 0, 2, 1, 8, 7, 0, 3, 6, 1, 9];

let heapSort = arr => {
    // 1. 构建大顶堆
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
        //从第一个非叶子结点从下至上，从右至左调整结构  
        adjustHeap(arr, i, arr.length);
    }

    // 2.调整堆结构+交换堆顶元素与末尾元素
    for (let j = arr.length - 1; j > 0; j--) {
        [arr[0], arr[j]] = [arr[j], arr[0]]; // 交换堆顶和末尾元素
        adjustHeap(arr, 0, j) // 重新对堆进行调整
    }
    return arr;
}

function adjustHeap(arr, i, len) {
    let temp = arr[i]; // 取出当前元素
    for (let k = i * 2 + 1; k < len; k = k * 2 + 1) { // 从i结点的左子结点开始，也就是2i+1处开始
        if (k + 1 < len && arr[k] < arr[k + 1]) { // 如果左子结点小于右子结点，k指向右子结点
            k++;
        }
        if (arr[k] > temp) { // 如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }
    arr[i] = temp; // 将temp值放到最终的位置
}

console.log(heapSort(arr))